//
//  堆排序.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/26.
//

import Foundation

struct Heap<T: Comparable> {
    /// 数组，从下标为1开始存储数据
    private var a: [T?]
    /// 堆可以存储的最大数据个数
    private var n: Int
    /// 堆中已有数据个数
    private var count: Int
    
    init(_ capacity: Int) {
        a = [T?].init(repeating: nil, count: capacity + 1)
        n = capacity
        count = 0
    }
    
    mutating func inset(_ data: T) {
        // 数组中下标为 i 的节点，左子节点就是下标为 i*2 的节点，右子节点就是下标为 i*2+1 的节点，父节点就是下标为 2/i​ 的节点。
        if count >= n {
            fatalError("堆已满，插入失败")
        }
        count += 1
        a[count] = data
        var i = count
        while i / 2 > 0 && a[i]! > a[i / 2]! {
            a.swapAt(i, i / 2)
            i /= 2
        }
    }
    
    mutating func removeMax() {
        if count == 0 {
            fatalError("堆中没有元素")
        }
        a[1] = a[count]
        a[count] = nil
        count -= 1
        heapify(&a, count, 1)
    }
    
    /// 自上而下堆化
    private func heapify(_ a: inout [T?], _ n: Int, _ i: Int) {
        while true {
            var i = i
            var maxPos = i
            if i * 2 <= n && a[i]! < a[i * 2]! {
                maxPos = i * 2
            }
            if i * 2 + 1 <= n && a[maxPos]! < a[i * 2 + 1]! {
                maxPos = i * 2 + 1
            }
            if maxPos == i {
                break
            }
            a.swapAt(maxPos, i)
            i = maxPos
        }
    }
    
    // MARK: - 类方法，堆排序
    private static func buildHeap(_ a: inout [T?], _ n: Int) {
        var i = n / 2
        while i >= 1 {
            heapify(&a, n, i)
            i -= 1
        }
    }
    
    private static func heapify(_ a: inout [T?], _ n: Int, _ i: Int) {
        var i = i
        while true {
            var maxPos = i
            if i * 2 <= n && a[i]! < a[i * 2]! {
                maxPos = i * 2
            }
            if i * 2 + 1 <= n && a[maxPos]! < a[i * 2 + 1]! {
                maxPos = i * 2 + 1
            }
            if maxPos == i {
                break
            }
            a.swapAt(i, maxPos)
            i = maxPos
        }
    }
    
    static func sort(_ a: inout [T?], _ n: Int) {
        buildHeap(&a, n)
        var k = n
        while k > 1 {
            a.swapAt(k, 1)
            k -= 1
            heapify(&a, k, 1)
        }
    }
}

// MARK: - 遵守CustomStringConvertible和CustomDebugStringConvertible协议
extension Heap: CustomStringConvertible, CustomDebugStringConvertible {
    var description: String {
        return a.description
    }
    
    var debugDescription: String {
        return a.debugDescription
    }
}
